//桶排序
//对额外存储空间的使用较大
//为了使排序尽量高效，需要尽量做到：（1）在额外空间充足的情况下，尽量增大桶的数量；（2）使用的映射函数能够将输入的N个数据尽量均匀的放入K个桶中
//对每个桶内元素的排序算法选择也很关键
//最快：数据可以均匀的分到每个桶；最慢：所有元素都被分到了一个桶

//步骤：1.找到原数组中最大元素max和最小元素min，根据设定好的每个桶的尺寸计算出有多少个桶
//2.根据arr[i]到min的差值决定arr[i]应该放在哪个桶内，距离越小，放的桶越靠前
//3.对每个桶内元素排序，排序算法的选择也很关键。将排好序的桶内元素依次放入arr。编号较小的桶内元素也较小，所以每个桶内进行排序即可，不用全部排序。

import java.util.Arrays;

public class bucketSort {
    public static void main(String[] args) {
        int[] arr = new int[]{3,4,3,2,6,7,7,1};
        //桶的尺寸
        int bucketSize = 4;
        int[] res = sort(arr,bucketSize);
        System.out.println(Arrays.toString(res));
    }

    public static int[] sort(int[] arr, int bucketSize){
        if(arr.length == 0){
            return arr;
        }
        int min = arr[0];
        int max = arr[0];
        for(int value : arr){
            if(value > max){
                max = value;
            }else if(value < min){
                min = value;
            }
        }
        //桶的数量
        int bucketCount = ((max - min) / bucketSize) + 1;
        int[][] buckets = new int[bucketCount][0];

        //将arr[i]映射到桶里
        for(int i = 0 ; i < arr.length ; i++){
            int index = (int) Math.floor((arr[i] - min) / bucketSize);
            buckets[index] = arrAppend(buckets[index],arr[i]);
        }

        int arrIndex = 0;
        //桶内排序
        for(int[] bucket : buckets){
            bucket = insertSort(bucket);
            for(int value : bucket){
                arr[arrIndex++] = value;
            }
        }
        return arr;
    }

    //扩容并保存数据
    public static int[] arrAppend(int[] arr, int value){
        arr = Arrays.copyOf(arr,arr.length+1);
        arr[arr.length-1] = value;
        return arr;
    }
}
